#include <iostream>
#include <vector>
using namespace std;
// 冒泡排序
// 从前往后两两比较，如果第二个数小，就swap，这样能保证最后一个数一定是最大的
void bubble_sort(vector<int> &nums, int n) {
    bool swapped;
    for (int i = 1; i < n; ++i) {
        swapped = false;
        for (int j = 1; j < n - i + 1; ++j) {
            if (nums[j] < nums[j - 1]) {
                swap(nums[j], nums[j - 1]);
                swapped = true;
            }
        }
        // swapped是标志，如果这一轮冒泡没有发生swap，那么证明已经排好序
        if (!swapped) {
            break;
        }
    }
}

// 选择排序
// 第n-1次遍历找min，与第n-1个数交换
void selection_sort(vector<int> &nums, int n) {
    int min;
    for (int i = 0; i < n - 1; ++i) {
        min = i;
        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums[min], nums[i]);
    }
}

// 插入排序
// 类似打扑克理牌
void insertion_sort(vector<int> &nums, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; --j) {
            swap(nums[j], nums[j - 1]);
        }
    }
}

// 快速排序
// 先选出主元pivot，比主元小的都放左边，比主元小的都放右边
void quick_sort(vector<int> &nums, int l, int r) {
    if (l + 1 > r) {
        return;
    }
    // 选取第一个元素为pivot，pivot选法会对复杂度产生很大影响
    int first = l, last = r - 1, pivot = nums[first];
    while (first < last) {
        // 执行完这个while之后，last到达了比pivot小的数据
        while (first < last && nums[last] >= pivot) {
            --last;
        }
        // 把比pivot小的数据放在first
        nums[first] = nums[last];
        // 执行完这个while之后，first到达了比pivot大的数据
        while (first < last && nums[first] <= pivot) {
            ++first;
        }
        // 把比pivot大的数据放在这个位置
        // nums[last]此时已经放在前面了，因此不用考虑数据丢失
        nums[last] = nums[first];
    }
    // 最终nums[first]出现了两次，因此把pivot放在这里，就完成了一次分组
    nums[first] = pivot;
    quick_sort(nums, l, first);
    quick_sort(nums, first + 1, r);
}

// 归并排序
// 将数组分组，每组内进行排序，然后合并
void merge_sort(vector<int> &nums, int l, int r, vector<int> &temp) {
    if (l + 1 >= r) {
        return;
    }
    // divide
    int m = l + (r - l) / 2;
    merge_sort(nums, l, m, temp);
    merge_sort(nums, m, r, temp);
    // conquer
    int p = l, q = m, i = l;
    while (p < m || q < r) {
        if (q >= r || (p < m && nums[p] <= nums[q])) {
            temp[i++] = nums[p++];
        }
        else {
            temp[i++] = nums[q++];
        }
    }
    for (i = l; i < r; ++i) {
        nums[i] = temp[i];
    }
}